N=1000;
m1=2;
m2=14;
S=[1,2,1,1,95569,3019,1,36809,191446,143102,2,1,25111,1595905543,2,1,2557183,2,2,15227,389588,1,1,155816062,1,50867,34378,1,1,81647,1,4,90659,70849,65519,1,92657,180014,1,1,1,50053,57899,696734347,2,1,1,145162702,2,29284,153991078,1,4,32117,31238,39829,18562,4,32957,57331,2,8609,6379,43291,274844,4,4,98678,2,2,4,4,37462,4,31649,99709,2,1,2,1,1,2,98074,15101,13582,163946,7927,2,8353,2,1,1,2,2,6317,83117,1,58054,1,1,1,97547,150218,2,4,1,1,17581,1,1,135297623,1,1,1,4,2,1,1,13923802,1,1,4,2,35246,2,8,1,7451,2,2,41878,2,1,1,2,91583,52201,1,1,61543,1,1,1,1,10313,20717,85531,2,540885419,1213943399,1,4,71146,406809118,192646,2,23053,1,100421521,165806,1673634316,2,17099,6551,1,94291,4,2,16879,2,298568,1174951681,9431,1,98533,1,542557514,47161,8,18443,1,2,17341,2,1,33874,169262,150989071,57653,43951,1,46082,141094231,377764,66919,4,2,2,2,588464,2,182866,10253,2,98327,9479,79427,1,16,1,4,1,4,1,1,1,160222,16,2,182566,2,74197,1,1,2,71821,2,158566,2,2,2,85411,170458,1,1,2,1,5743,1,1,1,17863,1,2,56594,1,1,1,1,1,22871,1,1,1623356209,2,94777,1,1,1,1,2,1,2,306716,22247,1,1,1,51839,23333,1,56489,1,1,1,96851,1,1,1,2,26003,141826,1,1801,2,2,86969,2,194426,59978,55694,73174,1,49123,42491,67138,1303,62201,1,54713,2,1,1,6661,2,2,2,2,1,1,91558,2,85334,1,1753,986658076,73586,38299,1,160694,1,56053,1,1,45022,2,30319,2,8,2,142526,1,1,492267037,31321,2,1,1,2,96926,66733,103126,1,1,191638,4538,162202,1,2,67934,72538,2,59518,1,1,2,80363,32843,87959,1,1,1,21313,2,4,18859,144986,4,1,1,8,70573,2,2,2,1,2,638754917,2578,1,4,2,2,1,1,2,38303,1,1,41519,2,1,1,1,1,1,1,4,2,26237,2,2,4,328868,4,16231,1,40699,18182,63997,65011,2,79201,66733,1,1,2,2,98887,21031,1,26227,1,2,95617,1,1,1,336916,1,1,2,1,559106459,2,1,2,2,176854,118886,1,1,1,1,1,181358,1,2,87988,1,314977538,1,29753,80378,4,1,1,76837,1,2,96587,1,362396,14479,1,1,4,96959,29819,1,11903,2,1,1,2,84977,54541,1,65414,196642,2,2,2,1,1,1,2,1,7177,382,1,158566,33911,1,2,4,2,1,4,1,4,2,72458,2,1,1,1,2,130618,31123,121778,2,6607,356624647,109814,62983,63607,2,57119,2,1,88861,2,34763,1,34649,2,1,10607,176248,36637,65789,1019,1,1,1,4,1,1,1,57238,30773,8,2,4,1,23578,4,1,44203,197,796936939,1933832843,1,164926,1,1,1,2,84247,4,76634,59209,1,57203,1,4,162238,1,1,2,70442,1,64038103,1,2,97298,9466,13499,1,1,1,2,1,2,47119,2,60169,1,1,51386,174854,1,2,1,2,1,23854,1,18257,1,2,1,66431,4957,1,104708,4,190478,2,3659,1,2,132094,1,1,2,1,63718,1,1,1,42178,1,4,2,1,1,1,4,482041202,1,1,8863,76204,55603,11906,1,2,1,1,1,158428,2,23203,1,38321,1,89923,1457311591,1,2,1,62017,12097,981154241,4,34913,1,314036,229556,2,1,1,2,1,515075623,2,1,59716,56437,1,1,769555277,49711,46411,7459,1,1,2,2,1,1683527002,27203263,1,2,1,47954,196754,22093,2,4,1,2,1,46261,1080612053,1,362788,98269,2,29717,2,142586,15809,44738,79589,22123,63311,1,222484,69403,526,1,1,401,2,192986,1,1,69061,154738,2,1,229652,95962,32443,19562,1,151982,33617,1,1,2,1,1636345153,1,1,195626,2,229192,95549,53069,183082,1,2,1,2,10193,1,2143,179038,1,2,11257,1,1,1,28753,2,56171,2,72218,2,1,1,1,1,1,1,27059,77191,1,2,71081,1952258927,40786,417882698,1,2,4,1243402441,136898,18482,587624,1226316922,11909,1,199960081,145742,2069,58067,2,2,221336341,1,1118261951,2,787012294,62659,35267,1,1257059002,1,1,1,1,18541,296788,132926,1,40123,1,1,27754,1,1,1,100442,1430560513,21101,8,4,1,1,32507,1,50047,4463,29668,1,5383349,2,1,2,1,49009,2,12907,84589,154942,51749,1,16,4363,2,7666,192838,81307,1,44071,45181,1,1,28697,25229,1,1,1,1,1,4651,2,4,1,1,82787,1,13163,1,1,1,1,1,2,98809,1,2,2,1,1,1,1,36299,4,1,121802,1,6247,108998,1,24611,2,67079,148574,51031,76541,19079,2,1,1,1,4,1,1,1,2,2,44386,1,4,1,1,2,457,1,1,1,1,4517,202684,75167,1,20386,1,1,2,49207,6791,1,1,4,1,4,1,1,292532,1,1,487944031,1,1,1,83761,2,348744509,453917473,332776,1,74941,85711,16,2,1,12073,2,2,1,4,2,1,4,1,1570628021,191194,1,1,1,77489,1,1,1,1,1,2,1,1449812519,2,92146,1,30977,1,25541,1,1033,2,1,1,4,2,142286,2,2,2,20143,1,182133719,1,198034,1];